<html>
<head>
<link rel="shortcut icon" href="./favicon.ico">
<link rel="stylesheet" type="text/css" href="./style.css">
<link rel="canonical" href="./Arbiter_Round_Robin.html">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="Returns a one-hot grant bitmask selected from one of the raised request bits in a word, in round-robin order, going from least-significant bit (highest priority) to most-significant bit (lowest priority), and back around. *A grant is held until the request is released.*">
<title>Arbiter Round Robin</title>
</head>
<body>

<p class="inline bordered"><b><a href="./Arbiter_Round_Robin.v">Source</a></b></p>
<p class="inline bordered"><b><a href="./legal.html">License</a></b></p>
<p class="inline bordered"><b><a href="./index.html">Index</a></b></p>

<h1>A Round-Robin Arbiter</h1>
<p>Returns a one-hot grant bitmask selected from one of the raised request
 bits in a word, in round-robin order, going from least-significant bit
 (highest priority) to most-significant bit (lowest priority), and back
 around. <em>A grant is held until the request is released.</em></p>
<p>Unset request bits are skipped, which avoids wasting time. Requests can be
 raised or dropped before their turn comes, but this must be done
 synchronously to the clock. <em>Grants are calculated combinationally from the
 requests</em>, so pipeline as necessary. If the <code>requests_mask</code> bit
 corresponding to a <code>requests</code> bit is zero, then that request cannot be
 granted that cycle. The round-robin always continues from the last granted
 request, even after an idle period of no requests, unless <code>clear</code> is
 asserted.</p>
<h2>Usage</h2>
<p>A common use-case for an arbiter is to drive a <a href="./Multiplexer_One_Hot.html">one-hot
 multiplexer</a> to select one of multiple senders
 requesting for one receiver, or one of multiple receivers requesting from
 one sender. This arrangement requires that the requestors can raise and
 hold a <code>requests</code> bit, wait until they receive the correspondig <code>grant</code> bit
 to begin their transaction, and to drop their <code>requests</code> bit only once they
 are done.  This is very similar to a ready/valid handshake, except that the
 transaction cannot be interrupted, else the granted access is lost.</p>
<h2>Fairness</h2>
<p>Here, we implement a "mask method" round-robin arbiter, as described in
 Section 4.2.4, Figure 12 of Matt Weber's <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.550&amp;rep=rep1&amp;type=pdf">Arbiters: Design Ideas and Coding
 Styles</a>. </p>
<p>A round-robin arbiter is commonly used to fairly divide a resource amongst
 multiple requestors, <em>in proportion to each requestor's activity</em>, since
 each requestor holds a grant until they lower their request. Idle
 requestors don't use up any of the arbitrated resource. A frequent
 requestor will not obstruct other requestors perpetually.</p>
<p>However, this round-robin arbiter does not deal with some subtleties of
 fairness. For example, it's possible that under normal operation, one
 requestor ends up placing a request always just before the previous
 requestor finishes. Thus, that new request waits less than the others. One
 solution periodically takes a snapshot of the current pending requests, and
 services all of these requests before refreshing the snapshot.</p>
<h3>Customizations</h3>
<p>To enable the creation of custom fairness adjustments, the <code>requests_mask</code>
 input can be used to exclude one or more requests from being granted in the
 current cycle, and must be updated synchronously to the <code>clock</code>. The
 <code>requests_mask</code> is arbitrary, and if desired can be calculated from the
 current <code>requests</code>, the <code>grant_previous</code> one-hot output which always holds
 the last given grant even if the requests are currently all idle, and the
 current one-hot <code>grant</code> output.</p>
<ul>
<li>Since a grant typically lasts longer than one cycle and won't get granted
 again for several cycles, taking multiple cycles to compute the next
 <code>requests_mask</code> is a valid option.</li>
<li>The <code>requests_mask</code> is applied combinationally to the <code>requests</code> input
 and to the internal <code>round_robin_mask</code>, both of which have a combinational
 path to <code>grant</code>, so pipeline as necessary. </li>
</ul>
<p>If unused, leave <code>requests_mask</code> set to all-ones, and the masking logic
 will optimize away.</p>

<pre>
`default_nettype none

module <a href="./Arbiter_Round_Robin.html">Arbiter_Round_Robin</a>
#(
    parameter INPUT_COUNT = 0
)
(
    input   wire                        clock,
    input   wire                        clear,

    input   wire    [INPUT_COUNT-1:0]   requests,
    input   wire    [INPUT_COUNT-1:0]   requests_mask,  // Set to all-ones if unused.
    output  wire    [INPUT_COUNT-1:0]   grant_previous,
    output  reg     [INPUT_COUNT-1:0]   grant
);

    localparam ZERO = {INPUT_COUNT{1'b0}};

    initial begin
        grant = ZERO;
    end
</pre>

<p>We need to detect if any requests are active: <em>when all requests go idle,
 we want to remember the last granted request.</em> Otherwise, that lost state
 means the round-robin restarts from the highest priority request rather
 than the next lower priority request after the last granted request. </p>
<p>Always granting the highest priority first after an idle period allows
 a pathological request pattern to cause starvation: all but the highest
 priority request would starve if they keep asserting and de-asserting in
 lock-step after an idle period.</p>

<pre>
    reg any_requests_active = 1'b0;

    always @(*) begin
        any_requests_active = (requests != ZERO);
    end
</pre>

<p>For the same reasons, we need to detect when we leave an idle request
 period so we can, for that cycle, refuse to grant again the last granted
 request, which would otherwise cause starvation of other requests happening
 in lock-step.</p>

<pre>
    wire out_from_idle;

    <a href="./Pulse_Generator.html">Pulse_Generator</a>
    requests_restart
    (
        .clock              (clock),
        .level_in           (any_requests_active),
        .pulse_posedge_out  (out_from_idle),
        // verilator lint_off PINCONNECTEMPTY
        .pulse_negedge_out  (),
        .pulse_anyedge_out  ()
        // verilator lint_on  PINCONNECTEMPTY
    );
</pre>

<p>Grant a request in priority order (LSB has higest priority) after applying
 <code>requests_mask</code>. This is the base case which starts the round-robin.</p>

<pre>
    reg [INPUT_COUNT-1:0] requests_masked_priority = ZERO;

    always @(*) begin
        requests_masked_priority = requests & requests_mask;
    end

    wire [INPUT_COUNT-1:0] grant_priority;

    <a href="./Bitmask_Isolate_Rightmost_1_Bit.html">Bitmask_Isolate_Rightmost_1_Bit</a>
    #(
        .WORD_WIDTH (INPUT_COUNT)
    )
    priority_grants
    (
        .word_in    (requests_masked_priority),
        .word_out   (grant_priority)
    );
</pre>

<p>Mask-off all requests <em>of equal and higher priority</em> than the request
 currently granted, from the previous cycle. This masking makes the
 round-robin progress towards lower priority requests as the previously
 granted higher priority requests are released. The <code>thermometer_mask</code> must
 be inverted before use.</p>

<pre>
    wire [INPUT_COUNT-1:0] thermometer_mask;

    <a href="./Bitmask_Thermometer_to_Rightmost_1_Bit.html">Bitmask_Thermometer_to_Rightmost_1_Bit</a>
    #(
        .WORD_WIDTH (INPUT_COUNT)
    )
    grant_mask
    (
        .word_in    (grant_previous),
        .word_out   (thermometer_mask)
    );

    reg [INPUT_COUNT-1:0] round_robin_mask = ZERO;

    always @(*) begin
        round_robin_mask = ~thermometer_mask;
    end
</pre>

<p>The <code>round_robin_mask</code> excludes the currently granted request, which we
 don't want to interrupt, so we OR the currently granted request bit into
 the <code>round_robin_mask</code> so we only mask-off all <em>higher</em> priority requests,
 leaving the currently granted request as highest priority.</p>
<p><strong>EXCEPTION:</strong> If we are returning from an all-idle request phase, we
 instead zero-out that granted request bit, so the round-robin can resume to
 the next lower priority request based on the <code>round_robin_mask</code>, instead of
 possibly re-granting the same request again.</p>
<p>The <code>round_robin_mask</code> is further masked, in the same manner, by the
 <code>requests_mask</code> input, which may prevent the granting of some <code>requests</code> of
 lower priority after the currently granted request is released.</p>

<pre>
    reg [INPUT_COUNT-1:0] requests_masked_round_robin   = ZERO;
    reg [INPUT_COUNT-1:0] grant_previous_gated          = ZERO;

    always @(*) begin
        grant_previous_gated        = (out_from_idle == 1'b1) ? ZERO : grant_previous;
        requests_masked_round_robin = requests & (round_robin_mask | grant_previous_gated) & (requests_mask | grant_previous_gated);
    end
</pre>

<p>Grant a request in priority order, but from the round-robin masked
 requests, which only contain requests of equal or lower priority to the
 currently granted request, minus any requests further masked by the
 <code>requests_mask</code> input.</p>

<pre>
    wire [INPUT_COUNT-1:0] grant_round_robin;

    <a href="./Bitmask_Isolate_Rightmost_1_Bit.html">Bitmask_Isolate_Rightmost_1_Bit</a>
    #(
        .WORD_WIDTH (INPUT_COUNT)
    )
    round_robin_grants
    (
        .word_in    (requests_masked_round_robin),
        .word_out   (grant_round_robin)
    );
</pre>

<p>If no round-robin granted requests remain, then instead grant from the
 priority requests, which starts over the round-robin at the highest
 priority (LSB) request.  This also resets <code>round_robin_mask</code>.</p>

<pre>
    always @(*) begin
        grant = (grant_round_robin == ZERO) ? grant_priority : grant_round_robin; 
    end
</pre>

<p>Remember the last granted request so we can compute <code>round_robin_mask</code> to
 exclude higher priority requests than the last granted request. If all
 requests go idle, don't update, so we can continue the round-robin from
 where we left off when requests appear again, to avoid starvation of lower
 priority requests.</p>

<pre>
    <a href="./Register.html">Register</a>
    #(
        .WORD_WIDTH     (INPUT_COUNT),
        .RESET_VALUE    (ZERO)
    )
    previously_granted_request
    (
        .clock          (clock),
        .clock_enable   (any_requests_active),
        .clear          (clear),
        .data_in        (grant),
        .data_out       (grant_previous)
    );

endmodule
</pre>

<hr>
<p><a href="./index.html">Back to FPGA Design Elements</a>
<center><a href="https://fpgacpu.ca/">fpgacpu.ca</a></center>
</body>
</html>

